#pragma once
#include <type_traits>
#include <iostream>
using std::ostream;

#include "../public/constants.hpp"
#include "../public/exception.hpp"
#include "../allocator/defaloc.hpp"
#include "../iterator/iterator_traits.hpp"

#include "../container/list.hpp"

namespace bla {
	const _containerSizeType _DEQUE_BUCKSIZE = 8;

	template<typename _type, typename _allocator>
	class deque;

	/*
	 * template para:
	 * _type : all container have, can be any type
	 * _allocator: here is useless
	 */
	template<typename _type, typename _allocator = _defaloc<_type>>
	class dequeIterator {
		friend class deque<_type, _allocator>;
	public:
		//using define
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;

		//interface of all iteraters
		typedef valueType _valueType;
		typedef differenceType _difType;
		typedef _random_iterator_flag _category;

	private:
		//class data define: size of dequeIterator<> class: 32
		pointerType _cur;
		pointerType _first;
		pointerType _last;
		listIterator<pointerType> _node;
	public:
		dequeIterator() :
			_cur(nullptr), _first(nullptr), _last(nullptr), _node(listIterator<pointerType>()) { ; };
		
		dequeIterator(const dequeIterator<_type, _allocator>&) = default;
		dequeIterator<_type, _allocator>& operator=(const dequeIterator<_type, _allocator>&) = default;

		referenceType operator *() { return *_cur; }
		const referenceType operator *()const { return *_cur; }
		pointerType operator ->() { return &(operator*()); }
		const pointerType operator ->()const { return &(operator*()); }

		dequeIterator<_type, _allocator>& operator ++() {
			this->_cur++;
			if (this->_cur == this->_last) {
				this->_node++;
				this->_first = *(this->_node);
				this->_last = this->_first + _DEQUE_BUCKSIZE;
				this->_cur = this->_first;
				return *this;
			}
			else return *this;
		};
		dequeIterator<_type, _allocator> operator ++(int) {
			auto temp = *this;
			++(*this);
			return temp;
		};
		dequeIterator<_type, _allocator>& operator --() {
			if (this->_cur == this->_first) {
				this->_node--;
				this->_first = *(this->_node);
				this->_last = this->_first + _DEQUE_BUCKSIZE;
				this->_cur = this->_last;
				this->_cur--;
				return *this;
			}
			else {
				this->_cur--;
				return *this;
			}
		};
		dequeIterator<_type, _allocator> operator --(int) {
			auto temp = *this;
			--(*this);
			return temp;
		};

		bool operator ==(const dequeIterator<_type, _allocator>& it)const {
			return this->_cur == it._cur && this->_first == it._first &&
				this->_last == it._last && this->_node == it._node;
		};
		bool operator !=(const dequeIterator<_type, _allocator>& it)const {
			return !(*this == it);
		};

		template<typename _type, typename _allocator>
		friend dequeIterator<_type, _allocator> operator+ (
			const dequeIterator<_type, _allocator>& it, typename dequeIterator<_type, _allocator>::differenceType n);

		template<typename _type, typename _allocator>
		friend dequeIterator<_type, _allocator> operator+ (
			typename dequeIterator<_type, _allocator>::differenceType n, const dequeIterator<_type, _allocator>& it);

		template<typename _type, typename _allocator>
		friend dequeIterator<_type, _allocator> operator- (
			const dequeIterator<_type, _allocator>& it, typename dequeIterator<_type, _allocator>::differenceType n);

		template<typename _type, typename _allocator>
		friend dequeIterator<_type, _allocator> operator- (
			typename dequeIterator<_type, _allocator>::differenceType n, const dequeIterator<_type, _allocator>& it);

		template<typename _type, typename _allocator>
		friend typename dequeIterator<_type, _allocator>::differenceType operator- (
			const dequeIterator<_type, _allocator>& it1, const dequeIterator<_type, _allocator>& it2);


		~dequeIterator() = default;
	};

	template<typename _type, typename _allocator>
	dequeIterator<_type, _allocator> operator+(const dequeIterator<_type, _allocator>& it, typename dequeIterator<_type, _allocator>::differenceType n)
	{
		dequeIterator<_type, _allocator> ret(it);
		typename dequeIterator<_type, _allocator>::differenceType remainDif = ret._last - ret._cur;
		if (remainDif > n) {
			ret._cur += n;
		}
		else {  //should change listnode
			typename dequeIterator<_type, _allocator>::differenceType changeListNodeNum = (n - remainDif) / _DEQUE_BUCKSIZE + 1;
			typename dequeIterator<_type, _allocator>::differenceType absCurLoc = (n - remainDif) % _DEQUE_BUCKSIZE;
			ret._node = ret._node + changeListNodeNum;
			ret._first = *(ret._node);
			ret._last = ret._first + _DEQUE_BUCKSIZE;
			ret._cur = ret._first + absCurLoc;
		}
		return ret;
	}

	template<typename _type, typename _allocator>
	dequeIterator<_type, _allocator> operator+(typename dequeIterator<_type, _allocator>::differenceType n, const dequeIterator<_type, _allocator>& it)
	{
		return operator+(it, n);
	}

	template<typename _type, typename _allocator>
	dequeIterator<_type, _allocator> operator-(const dequeIterator<_type, _allocator>& it, typename dequeIterator<_type, _allocator>::differenceType n)
	{
		dequeIterator<_type, _allocator> ret(it);
		typename dequeIterator<_type, _allocator>::differenceType remainDif = ret._cur - ret._first;
		if (remainDif >= n) {
			ret._cur -= n;
		}
		else {  //should change listnode
			typename dequeIterator<_type, _allocator>::differenceType changeListNodeNum = (n - 1 - remainDif) / _DEQUE_BUCKSIZE + 1;
			typename dequeIterator<_type, _allocator>::differenceType absCurLoc = (_DEQUE_BUCKSIZE - 1) - (n - 1 - remainDif) % _DEQUE_BUCKSIZE;
			ret._node = ret._node - changeListNodeNum;
			ret._first = *(ret._node);
			ret._last = ret._first + _DEQUE_BUCKSIZE;
			ret._cur = ret._first + absCurLoc;
		}
		return ret;
	}

	template<typename _type, typename _allocator>
	dequeIterator<_type, _allocator> operator-(typename dequeIterator<_type, _allocator>::differenceType n, const dequeIterator<_type, _allocator>& it)
	{
		return operator-(it, n);
	}

	//note: it2 must > it1
	template<typename _type, typename _allocator>
	typename dequeIterator<_type, _allocator>::differenceType operator-(const dequeIterator<_type, _allocator>& it1, const dequeIterator<_type, _allocator>& it2)
	{
		typename dequeIterator<_type, _allocator>::differenceType changeListNodeNum = it1._node - it2._node;
		typename dequeIterator<_type, _allocator>::differenceType absCurLoc = (it1._cur - it1._first) - (it2._cur - it2._first);
		return _DEQUE_BUCKSIZE*changeListNodeNum + absCurLoc;
	}

	/*
	 * template para:
	 * _type : all container have, can be any type
	 * _allocator: suggest using the default value: the default is _defaloc class
	 */
	template<typename _type, typename _allocator = _defaloc<_type>>
	class deque {
		friend class dequeIterator<_type, _allocator>;
	public:
		//using define
		using iterator = dequeIterator<_type, _allocator>;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
	private:
		//class data define: size of forwadList<> class: 16
		iterator _begin;
		iterator _end;
		list<pointerType> _innerList;
		_allocator _allocatorObject;
	public:
		inline const sizeType size() const { return this->_end - this->_begin; };
		inline const iterator begin() const { return this->_begin; };
		inline const iterator end() const { return this->_end; };
		inline bool empty() const { return this->_end == this->_begin; };

		referenceType operator[] (differenceType n) {
			return *(this->_begin + n);
		}

		/*
		 * push_back: const _type& v
		 *     add a value/object in the end
		 */
		void push_back(const _type& v) {
			if (!std::is_trivially_copy_constructible<_type>::value) {
				_allocatorObject._construct(this->_end._cur, v);
			}
			else {
				*(this->_end._cur) = v;
			}

			this->_end++;
			if (this->_end._node == this->_innerList.end()) {
				pointerType _newPtr = _allocatorObject._allocate(_DEQUE_BUCKSIZE);
				this->_innerList.push_back(_newPtr);
				this->_end._first = _newPtr;
				this->_end._cur = _newPtr;
				this->_end._last = _newPtr + _DEQUE_BUCKSIZE;
			}
		}

		/*
		 * push_front: const _type& v
		 *     add a value/object in the beginning
		 */
		void push_front(const _type& v) {
			if (this->_begin._cur == this->_begin._first && this->_begin._node == this->_innerList.begin()) {
				pointerType _newPtr = _allocatorObject._allocate(_DEQUE_BUCKSIZE);
				this->_innerList.insert(this->_innerList.begin(), _newPtr);
			}

			this->_begin--;
			if (!std::is_trivially_copy_constructible<_type>::value) {
				_allocatorObject._construct(this->_begin._cur, v);
			}
			else {
				*(this->_begin._cur) = v;
			}
		}

		/*
		 * pop_back
		 *     if not empty, remove a value/object in the end, return true;
		 *     else return false;
		 */
		bool pop_back() {
			if (this->empty()) return false;
			else {
				this->_end--;
				if (!std::is_trivially_destructible<_type>::value) {
					_allocatorObject._destroy(this->_end._cur);
				}
				return true;
			}
		}

		/*
		 * pop_front
		 *     if not empty, remove a value/object in the beginning, return true;
		 *     else return false;
		 */
		bool pop_front() {
			if (this->empty()) return false;
			else {
				if (!std::is_trivially_destructible<_type>::value) {
					_allocatorObject._destroy(this->_begin._cur);
				}
				this->_begin++;
				return true;
			}
		}
	private:
		/*
		 * _insertFrontPri: iterator it, const _type& v
		 *     add a value/object at it, grow to the front
		 *
		 * note: if call the function ,makesure that it belongs to *this, *this.size() > 0, it != this.begin()
		 */
		void _insertFrontPri(iterator it, const _type& v) {
			//push_front
			this->push_front(*this->_begin);
			//move 
			differenceType _insertLoc = it - this->_begin - 1;
			for (differenceType _index = 0; _index < _insertLoc; ++_index) {
				this->operator[](_index) = this->operator[](_index + 1);
			}
			//sustitute
			this->operator[](_insertLoc) = v;
		}

		/*
		 * _insertBackPri: iterator it, const _type& v
		 *     add a value/object at it, grow to the back
		 * note: if call the function ,makesure that it belongs to *this, *this.size() > 0, it != this.end()
		 */
		void _insertBackPri(iterator it, const _type& v) {
			//push_back
			this->push_back(*(this->_end - 1));
			//move 
			differenceType _insertLoc = it - this->_begin;
			for (differenceType _index = (this->size() - 2); _index > _insertLoc; --_index) {
				this->operator[](_index) = this->operator[](_index - 1);
			}
			//sustitute
			this->operator[](_insertLoc) = v;
		}

		/*
		 * _insertFrontPri: iterator it, iterator cpbeg, iterator cpend
		 *     add some value/objects at it, grow to the front
		 *
		 * note: if call the function ,makesure that it belongs to *this, *this.size() > 0
		 * note:must ensure that cpbeg and cpend belong to the same deque(and not *this deque), and cpend must >= cpbeg
		 */
		void _insertFrontPri(iterator it, iterator cpbeg, iterator cpend) {
			const differenceType _remainValueNum = it - this->_begin;
			const differenceType _insertNum = cpend - cpbeg;
			if (_remainValueNum >= _insertNum){
				//push_front
				const differenceType _startPushLoc = _insertNum - 1;
				for (differenceType _index = _startPushLoc; _index >= 0; --_index) {
					this->push_front(this->operator[](_startPushLoc));
				}
				//move
				const differenceType _startMoveLoc = _startPushLoc + _remainValueNum;
				differenceType _preLoc = 2 * _insertNum;
				for (differenceType _time = 0; _time < (_remainValueNum - _insertNum); ++_time) {
					this->operator[](_preLoc - _insertNum) = this->operator[](_preLoc);
					_preLoc++;
				}
				//substitute
				_preLoc = _startMoveLoc;
				iterator _cpIter = cpend - 1;
				for (differenceType _time = 0; _time < _insertNum; ++_time) {
					this->operator[](_preLoc--) = *(_cpIter--);
				}
			}
			else {
				iterator _cpIter = cpbeg + _insertNum - _remainValueNum - 1;
				//push_front, first part of cp
				for (differenceType _time = 0; _time < (_insertNum - _remainValueNum); ++_time) {
					this->push_front(*(_cpIter--));
				}
				//push_front, second part of *this
				const differenceType _startPushLoc = _insertNum  - 1;
				for (differenceType _index = _startPushLoc; _index >= (_insertNum - _remainValueNum); --_index) {
					this->push_front(this->operator[](_startPushLoc));
				}
				//substitute
				_cpIter = cpbeg + _insertNum - _remainValueNum;
				differenceType _preLoc = _insertNum;
				for (; _cpIter != cpend; ++_cpIter) {
					this->operator[](_preLoc++) = *(_cpIter);
				}
			}
		}

		/*
		 * _insertBackPri: iterator it, iterator cpbeg, iterator cpend
		 *     add some value/objects at it, grow to the back
		 *
		 * note: if call the function ,makesure that it belongs to *this, *this.size() > 0
		 * note:must ensure that cpbeg and cpend belong to the same deque(and not *this deque), and cpend must >= cpbeg
		 */
		void _insertBackPri(iterator it, iterator cpbeg, iterator cpend) {
			const differenceType _remainValueNum = this->_end - it;;
			const differenceType _insertNum = cpend - cpbeg;
			if (_remainValueNum >= _insertNum) {
				//push_back
				const differenceType _startPushLoc = this->size() - _insertNum;
				differenceType _preLoc = _startPushLoc;
				for (differenceType _time = 0; _time < _insertNum; ++_time) {
					this->push_back(this->operator[](_preLoc++));
				}
				//move
				const differenceType _endMoveLoc = it - this->_begin;
				const differenceType _startMoveLoc = _startPushLoc - 1;
				_preLoc = _startMoveLoc;
				for (; _preLoc >= _endMoveLoc; --_preLoc) {
					this->operator[](_preLoc + _insertNum) = this->operator[](_preLoc);
				}
				//substitute
				_preLoc = _endMoveLoc;
				iterator _cpIter = cpbeg;
				for (differenceType _time = 0; _time < _insertNum; ++_time) {
					this->operator[](_preLoc++) = *(_cpIter++);
				}
			}
			else {
				iterator _cpIter = cpend - (_insertNum - _remainValueNum);
				//push_back, first part of cp
				for (differenceType _time = 0; _time < (_insertNum - _remainValueNum); ++_time) {
					this->push_back(*(_cpIter++));
				}
				//push_back, second part of *this
				const differenceType _startPushLoc = it - this->_begin;
				differenceType _preLoc = _startPushLoc;
				for (differenceType _time = 0; _time < _remainValueNum; ++_time) {
					this->push_back(this->operator[](_preLoc++));
				}
				//substitute
				_cpIter = cpend - (_insertNum - _remainValueNum);
				_preLoc = _startPushLoc;
				for (iterator _loopIter = cpbeg; _loopIter != _cpIter; ++_loopIter) {
					this->operator[](_preLoc++) = *(_loopIter);
				}
			}
		}

		/*
		 * _eraseFrontPri: iterator it
		 *     erase a value/object at it, from the front to move
		 *
		 * note: if call the function ,makesure that it belongs to *this, *this.size() > 0
		 * must ensure that this->size() > 0
		 */
		void _eraseFrontPri(iterator it) {
			//move 
			differenceType _moveLoc = it - this->_begin;
			for (; _moveLoc > 0; --_moveLoc) {
				this->operator[](_moveLoc) = this->operator[](_moveLoc - 1);
			}
			this->pop_front();
		}

		/*
		 * _eraseBackPri: iterator it
		 *     erase a value/object at it, from the back to move
		 * note: if call the function ,makesure that it belongs to *this, *this.size() > 0, it != this.end()
		 * must ensure that this->size() > 0
		 */
		void _eraseBackPri(iterator it) {
			differenceType _moveLoc = it - this->_begin;
			for (; _moveLoc < (this->size() - 1); ++_moveLoc) {
				this->operator[](_moveLoc) = this->operator[](_moveLoc + 1);
			}
			this->pop_back();
		}

		/*
		 * _eraseFrontPri: iterator cpbeg, iterator cpend
		 *     erase some value/objects from cpbeg to cpend, from the front to move
		 *
		 * note: if call the function ,makesure that cpbeg and cpend belongs to *this, *this.size() > 0
		 * note: must ensure that cpend >= cpbeg
		 */
		void _eraseFrontPri(iterator cpbeg, iterator cpend) {
			//move
			const differenceType _eraseNum = cpend - cpbeg;
			differenceType _moveLoc = cpend - 1 - this->_begin;
			for (; _moveLoc > 0; --_moveLoc) {
				this->operator[](_moveLoc) = this->operator[](_moveLoc - _eraseNum);
			}
			//pop_front
			for (differenceType _time = 0; _time < _eraseNum; ++_time) {
				this->pop_front();
			}
		}

		/*
		 * _eraseBackPri: iterator cpbeg, iterator cpend
		 *     erase some value/objects from cpbeg to cpend, from the back to move
		 *
		 * note: if call the function ,makesure that cpbeg and cpend belongs to *this, *this.size() > 0
		 * note: must ensure that cpend >= cpbeg
		 */
		void _eraseBackPri(iterator cpbeg, iterator cpend) {
			//move
			const differenceType _eraseNum = cpend - cpbeg;
			differenceType _moveLoc = cpbeg - this->_begin;
			differenceType _remainMoveNum = this->_end - cpend;
			for (differenceType _time = 0; _time < _remainMoveNum; ++_time) {
				this->operator[](_moveLoc) = this->operator[](_moveLoc + _eraseNum);
				_moveLoc++;
			}
			//pop_back
			for (differenceType _time = 0; _time < _eraseNum; ++_time) {
				this->pop_back();
			}
		}

	public:
		/*
		 * insert: iterator it, const _type& v
		 *     add a value/object in iter
		 *
		 *     call func: _insertFrontPri and _insertBackPri
		 */
		void insert(iterator it, const _type& v) {
			//note: if this->_end == this->_begin, use the it == this->_end if condition!

			if (it == this->_end) this->push_back(v);
			else if (it == this->_begin) this->push_front(v);
			else {
				if ((it - this->_begin) < (this->_end - it)) {
					this->_insertFrontPri(it, v);
				}
				else {
					this->_insertBackPri(it, v);
				}
			}
		}

		/*
		 * insert: iterator it, iterator cpbeg, iterator cpend
		 *     add some value/object at it
		 *
		 *     call func: _insertFrontPri and _insertBackPri
		 */
		void insert(iterator it, iterator cpbeg, iterator cpend) {
			if ((it - this->_begin) < (this->_end - it))
			{
				this->_insertFrontPri(it, cpbeg, cpend);
			}
			else{
				this->_insertBackPri(it, cpbeg, cpend);
			}
		}

		/*
		 * erase: iterator it
		 *     erase a value/object of iter
		 *
		 *     call func: _eraseFrontPri and _eraseBackPri
		 *     must ensure that it belongs to *this, and this->size() > 0
		 */
		void erase(iterator it) {
			if ((it - this->_begin) < (this->_end - it)) {
				this->_eraseFrontPri(it);
			}
			else {
				this->_eraseBackPri(it);
			}
		}

		/*
		 * erase: iterator cpbeg, iterator cpend
		 *     erase some value/objects from cpbeg to cpend
		 *
		 *     call func: _eraseFrontPri and _eraseBackPri
		 *     must ensure that it belongs to *this, and this->size() > 0
		 */
		void erase(iterator cpbeg, iterator cpend) {
			if ((cpbeg - this->_begin) < (this->_end - cpend)) {
				this->_eraseFrontPri(cpbeg, cpend);
			}
			else {
				this->_eraseBackPri(cpbeg, cpend);
			}
		}

		/*
		 * default construction function:
		 *     init private values, call function of _allocatorObject to allocate memory,
		 *         if _type is not trivially_constructible, should call _construct of _allocatorObject
		 */
		deque() :
			_begin(iterator()), _end(iterator()),
			_innerList(list<pointerType>()), _allocatorObject(_allocator())
		{
			//in default, create two bucks
			pointerType _newPtrLeft = _allocatorObject._allocate(_DEQUE_BUCKSIZE);
			pointerType _newPtrRight = _allocatorObject._allocate(_DEQUE_BUCKSIZE);
			this->_innerList.push_back(_newPtrLeft);
			this->_innerList.push_back(_newPtrRight);

			this->_begin._cur = _newPtrRight;
			this->_begin._first = _newPtrRight;
			this->_begin._last = _newPtrRight + _DEQUE_BUCKSIZE;

			listIterator< pointerType> iter = this->_innerList.begin();
			iter++;
			this->_begin._node = iter;
			this->_end = this->_begin;
		}

		/*
		 * copy construction function:
		 *     init private values, call push_back
		 */
		deque(const deque<_type, _allocator>& d) :
			_begin(iterator()), _end(iterator()),
			_innerList(), _allocatorObject(_allocator())
		{
			//in default, create two bucks
			pointerType _newPtrLeft = _allocatorObject._allocate(_DEQUE_BUCKSIZE);
			pointerType _newPtrRight = _allocatorObject._allocate(_DEQUE_BUCKSIZE);
			this->_innerList.push_back(_newPtrLeft);
			this->_innerList.push_back(_newPtrRight);

			this->_begin._cur = _newPtrRight;
			this->_begin._first = _newPtrRight;
			this->_begin._last = _newPtrRight + _DEQUE_BUCKSIZE;

			listIterator< pointerType> iter = this->_innerList.begin();
			iter++;
			this->_begin._node = iter;
			this->_end = this->_begin;

			for (dequeIterator<_type> iter = d.begin(); iter != d.end(); ++iter) {
				this->push_back(*iter);
			}
		}

		/*
		 * = assign function: call push_back/pop_back
		 */
		const deque<_type, _allocator>& operator=(const deque<_type, _allocator>& d) {
			if (&d == this)
				return *this;
			else {
				dequeIterator<_type> _rawIterPre = this->_begin;
				dequeIterator<_type> _dIterPre = d.begin();
				const dequeIterator<_type> _rawIterEnd = this->_end;
				const dequeIterator<_type> _dIterEnd = d.end();
				
				while (_rawIterPre != _rawIterEnd && _dIterPre != _dIterEnd) {
					*(_rawIterPre++) = *(_dIterPre++);
				}

				if (_rawIterPre != _rawIterEnd) { //raw more long!, call pop_back!
					while (_rawIterPre != this->_end) {
						this->pop_back();
					}
				}
				else {  //d more long!, call push_back
					while (_dIterPre != _dIterEnd) {
						this->push_back(*(_dIterPre++));
					}
				}
				return *this;
			}
		}

		/*
		 * deconstruction function: if not is_trivially_copy_constructible, extra call _allocatorObject._destroy first
		 *                          always call _allocatorObject._allocate
		 */
		~deque() {
			if (!std::is_trivially_copy_constructible<_type>::value) {
				dequeIterator<_type, _allocator> diter = this->_begin;
				for (; diter != this->_end; ++diter) {
					_allocatorObject._destroy(diter._cur);
				}
			}

			listIterator<pointerType> iter = this->_innerList.begin();
			for (; iter != this->_innerList.end(); ++iter) {
				_allocatorObject._deallocate(*iter);
			}
		}

		template<typename _type, typename _allocator = _defaloc<_type>>
		friend ostream& operator<< (ostream &os, const deque<_type, _allocator>& li);
	};

	template<typename _type, typename _allocator = _defaloc<_type>>
	ostream & operator<<(ostream & os, typename const deque<_type, _allocator>& a)
	{
		typename deque<_type, _allocator>::iterator iter = a.begin();
		for (; iter != a.end(); ++iter) {
			os << *iter << " ";
		}
		return os;
	}
}
